# filename: solver.sage
# reference: https://cryptologie.net/article/371/fault-attacks-on-rsas-signatures/

import hashlib
import fractions
import json

# openssl x509 -inform der -text -noout -in Facebook.cer
modulus = 0xC8E3F7CA31F13A4D08DCD3C9E10D470EF266A80A3111D2CC68D0A22F19153526702D33CC5E7BA8662915CE776C399F6DD9B01EE0FFFD2F53DF83EDF98DF9B17BDE89CE4E9D0178AE16616568EB0A978C81C516ADE856ABFD48C133D03664982663158926BDD331A869CD931615B483EB84106120603E55FAEF5C5CE10EF9A2663475F7003723C662E4E04D1F7398DC9F939B377BBC9F612F6067E694E079A8C783602B2A70ECE1D500DE614D9D15D81DE9191F5CE95A1178788E5D7384283F1065B0FA2CCCAE54EE8AF9C124956E7ADAC874089A3DAA7F3E153D6D1BA902EDDD6D537B69B58FCC039B9484B1835B7E167D7B60138D9E211D353AF8BE8730BCDB
public_exponent = 65537

client_nonce = "57b3c6a014f3bf75e49d99a7502a9cc94af24b26a05d06bc2eeefebe44ac7431"
server_nonce = "e98405e4b8801a69c54f067e094f6f3dc1c4e2f3937af72d9ae4a4ddd116392c"
server_params = "03001741046bdb6948d2ee1ad618f5718bd6f749a7f9e56109a235f3274be0a4a809d8764bc1ecd561a28b6d2cd45b2beb1570d64c2f0a4109dd1c39cbf193f855650a2d75"
signature = 0x85467d0a99623e161a3127a1a0803d9eb3ca3ac924fa289e26262dc0f67ddfdeb3f24ff7593e479c41ff7372e53eebdf729010e71b496a8d3136d5a315ab8627fb02afb06ce0e44539a493fe2654ef742986bf0883c42af22b1f180b3ddbe008559924be18716658a99f649799e989dbcfab5a2c520f41904cdcb6a8ead161af07090ad9e14797b6d9ba458acef7807f6124caa03bb3a65a6794be6214e72f04bf574f7605cf04dd80165e268751096de62781ebd0edf7d05609c9002149db7a63683060706c6c348bc3fe0e77e4b16db12d8312aa1ab6e4fc43e643ac03f6a16d29412b59d247ec1e90534dad1f05949f281f9b5c13330e6e9208edac02eb1f


# hash the signed_params
h = hashlib.sha384()
h.update(client_nonce.decode('hex'))
h.update(server_nonce.decode('hex'))
h.update(server_params.decode('hex'))
hashed_m = h.hexdigest()

# PKCS#1 v1.5 padding
prefix_sha384 = "3041300d060960864801650304020205000430"

# modulus_len = (len(bin(modulus)) - 2 + 7) // 8
pad_len = len(hex(modulus))//2 - 3 - len(hashed_m)//2 - len(prefix_sha384)//2

padded_m = "0001" + "ff" * pad_len + "00" + prefix_sha384 + hashed_m

# Attack to recover p
p = gcd(signature^public_exponent - int(padded_m, 16), modulus)

# recover private key
q = modulus // p

print "[+] p:", p
print "[+] q:", q

# [+] p: 175653817257988201872252461398014869917210874225448853815003947930455935718534599483648554364757192366777027353365686842637995245093817814681006694875563701749129380610245872302970760270178135267229182769865703809227042886311647300800244451485605724712789402082075692990708504289797644360642232301210951972497
# [+] q: 144375320529052563170771758136112981391320084191761405050100262698945023053917998934210557907437462850513877566391181801636784425109438166703467644073942904234072642337257376564706436275310549261709409447376094316557269103645124842590803426379133094214931175879865854394612579684959706322609923567196668488363

# python rsatool.py -p 175653817257988201872252461398014869917210874225448853815003947930455935718534599483648554364757192366777027353365686842637995245093817814681006694875563701749129380610245872302970760270178135267229182769865703809227042886311647300800244451485605724712789402082075692990708504289797644360642232301210951972497 -q 144375320529052563170771758136112981391320084191761405050100262698945023053917998934210557907437462850513877566391181801636784425109438166703467644073942904234072642337257376564706436275310549261709409447376094316557269103645124842590803426379133094214931175879865854394612579684959706322609923567196668488363 -o out.key

# flag{nevergonnagiveyouup}